perm filename SEARCH[BOO,JMC] blob
sn#474745 filedate 1979-09-17 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00007 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 .if false then begin "questions and ideas"
C00004 00003 .s(SEARCH,LISP PROGRAMS FOR SEARCHING)
C00006 00004 .ss(insan,Depth First Tree Search.)
C00021 00005 .ss(minmax,Game trees.)
C00053 00006 .ss(trick,The hidden board trick.)
C00058 00007 .ss(tictactoe,2-dimensional Tic Tac Toe.)
C00075 ENDMK
C⊗;
.if false then begin "questions and ideas"
In section minmax ⊗imval applies to reasonably static positions.
What is meant by the term "static position?"
Movemax,movemin is a crock. bestminmax fns do not! call each other
recursively, they simply remember what move corresponds to the best
value when applying vmin or vmax to the list of successors.
No provision is made for the no successors case.
How fix? What really is intended??
What good do ALPHA and BETA -CUTOFF do.
Lmin seems to return only BETA whether β is too low or α is to hi
Similarly for lmax.
Add a discussion of breadth first search and example.
--test if string is in language generated by pdn system
--shortest path in graph, diameter, etc.
CH10[206,JMC]
ideas for fancier searching fns
Exercise for end of tree search section:
solve some other puzzle such as the block fitting puzzle using search
.end "questions and ideas"
.s(SEARCH,LISP PROGRAMS FOR SEARCHING)
.if NOTASSEMBLING then start
.EXTEND: NEXT SECTION!;
.ABSNTX: NEXT SECTION!;
.COMPIL: NEXT SECTION!;
.COMPUT: NEXT SECTION!;
.end
Many programs use the technique of exploring a "search space" of
possible solutions in order to solve a problem. It is often convenient
to represent the search space as
a tree structure with a starting position and some method of getting
to successor positions. In this case the search can be controlled by
some standard algorithm for visiting all nodes of a tree.
In this chapter we will examine various algorithms for
searching. The key feature in all cases is the ablility to separate
the problem into a basic recursive control program that describes the
search and a collection of problem dependent functions.
We give examples of specific problems and the collection of functions
that characterize the problem for each case.
Searching is an important tool in Artificial Intelligence
research and much work has been done on various techniques.
Most books treating AI discuss searching.
For an introduction to the general topic of searching techniques see
Nilsson[1971].
.ss(insan,Depth First Tree Search.)
One algorithm for searching a tree like structure
is the depth first search. It consists of taking the first (in some
fixed ordering) untried branch at each level until a leaf (terminal position)
is reached or until no more branches are left. In either case pop up one level and
continue the search until all nodes have been visited.
Simple S-expression recursion can be regarded as a special case
of depth first recursion. It is special in that there are exactly two
branches, but even more important, the tree is the tree of parts of
the S-expression and is present at the beginning of the calculation.
In the general case of tree search recursion, the tree is generated by
a ⊗successors function. We can describe the tree search in a problem
independent way by the general depth first tree search function ⊗search.
We have already seen a simple application of ⊗search in the problem of finding
a path to a particular node in a graph (Chapter {subsection treerec!}).
We recall here the definition of ⊗search.
.begin turnoff "{}" group
!fcnsearch&1 ⊗⊗⊗search p ← qif lose p qthen $LOSE qelse qif ter p qthen p qelse searchlis[successors p]⊗
where
!fcnsearchlis&1 ⊗⊗⊗ searchlis u ← qif qn u qthen $LOSE
qelse {search qa u}[λx: qif x = $LOSE qthen searchlis qd u qelse x]⊗.
.end
In order to solve a search problem using ⊗search we must be able to
characterize the problem in terms of the auxiliary functions
⊗successors, ⊗ter, and ⊗lose used by ⊗search.
As a nontrivial example we show how
to solve the so-called %3Instant Insanity%1 puzzle using ⊗search.
First we must describe the puzzle.
There are four cubical blocks, and each face of each block is colored with
one of four colors. The object of the puzzle is to build a tower of all four
blocks such that each vertical face of the tower involves all four colors.
In order to use the above defined function ⊗search for this purpose,
we must decide on a representation of positions and give the functions
⊗lose, ⊗ter, and ⊗successors. A position will be represented by a list
of lists - one for each face of the tower. Each sublist is the list of colors
of the faces of the blocks showing in that face. Initially the tower is
empty. The successors of a position are obtained by adding the next
unused block in all possible orientations, eg. by adding the appropriate
color to each of the four sublists. We shall assume that the
blocks are described in the following longwinded but convenient way. (We'll
take up precomputing this description later.)_ For each block there is a list
of the 24 orientations of the block where each orientation is described as
a list of the colors around the vertical faces of the block when it is in that
orientation. Thus the puzzle is described by a list of lists of lists which
we shall call ⊗puzz.
We now have
.begin nofill group turnon "∂"
.n←12
!fcnlose&puz ∂(n)⊗⊗lose p ← orlis[λu: ¬qn u ∧ qa u ε qd u, p],⊗
!fcnter&puz ∂(n)⊗⊗ ter p ← [length qa p = 4], ⊗
!fcnsuccessors&puz ∂(n)⊗⊗successors p ← mapcar[λx: mapcar2[λyz: z.y, p, x], nth[puzz, 1 + length qa p]]⊗
.end
where the functions ⊗mapcar2 and ⊗nth are given by
.begin nofill group turnon "∂"
.n←12
!fcnmapcar2& ∂(n)⊗⊗mapcar2[f, u, v] ← qif qn u qthen qNIL qelse
f[qa u, qa v] . mapcar2[f, qd u, qd v]⊗.
!fcnnth& ∂(n)⊗⊗nth[u, n] ← qif n=1 qthen qa u qelse nth[qd u, n-1]⊗.
.end
⊗nth picks out the list repesenting the next block in ⊗puzz. The outer mapping
functon runs through the list of orientations returned by ⊗nth and makes a new
position for each one. This is done by the inner mapping function which runs
simultaneously through the list tower faces and block faces, putting the block
face on the tower face.
A solution to the puzzle is obtained by assigning a value to ⊗puzz and
evaluating ⊗search[p0] with
⊗⊗⊗ p0 = $$(qNIL qNIL qNIL qNIL)$. ⊗
Obtaining ⊗puzz in the desired form is as complicated
a computation as the actual tree search. It can be
conveniently done by a sequence of assignment
statements starting with the following description of the blocks:
⊗⊗⊗puzz1 ← $$((G B B W R G) (G G B G W R) (G W W R B R) (G G R B W W))$⊗.
Here each block is represented by a list of the colors of the faces starting
with the top face, going around the sides in a clockwise direction and
finishing with the bottom face.
We need to go from this description of the blocks to a list of the
possible cycles of colors on the vertical faces for the 24 orientations of
the block. This not easy, because the order in which we have given the colors
is not invariant under rotations of the block. An easy way out is to start with
a block whose faces are assigned the numbers 1 thru 6 starting with the top,
going clockwise around the sides and finishing with the bottom. We write down
one cycle of side colors for each choice of the face put on top and get the
list of all 24 cycles by appending the results of generating the cyclic
permutations of the cycles. All this is accomplished by the assignment,
.begin nofill group
⊗⊗⊗puzz2 ← cycles[$$(2 3 4 5)$] * cycles[$$(2 5 4 3)$] * cycles[$$(1 2 6 4)$]⊗
⊗⊗⊗ * cycles[$$(1 4 6 2)$] * cycles[$$(1 3 6 5)$] * cycles[$$(1 5 6 3)$]⊗,
.end
where the function ⊗cycles is defined by
.begin nofill group
!fcncycles& ⊗⊗⊗ cycles u ← maplist[λv: v * upto[u, v], u] ⊗
!fcnupto& ⊗⊗⊗upto[u, v] ← qif v = u qthen qNIL qelse qa u . upto[qd u, v]⊗.
.end
Next we create a list of substitution lists, one for each block,
expressing the colors of the six numbered faces. This is done by the assignment
⊗⊗⊗puzz3 ← mapcar[λv: mapcar2[cons, $$(1 2 3 4 5 6)$, v], puzz1]⊗.
We use these substitutions to get for each block the list of 24 orientations
of the block. Thus
⊗⊗⊗puzz4 ← mapcar[[λs: mapcar[[λu: mapcar[[λx: qd assoc[x, s]], u]], puzz2]], puzz3]⊗
⊗puzz4 has all 24 orientations of the first block while for symmetry
reasons we need only consider three as distinct, say the first, ninth, and
seventeenth. So we finally get
⊗⊗⊗puzz ← <nth[qa puzz4, 1], nth[qa puzz4, 9],
nth[qa puzz4, 17]> . qd puzz4⊗.
The program when compiled runs about 11 seconds on the KA-10.
Interpreted it runs in 2-3 seconds on the KL-10. And we have
⊗⊗⊗search[p0] = $$((G W R B) (R W G B) (B R G W) (W B G R))$⊗
The descriptions for making ⊗puzz3 and ⊗puzz4 make heavy use of mapping
functions, which sometimes obscures what is really going on. Alternate
descriptions for these constructions are given by the following assignments
.begin nofill turnoff "{}" turnon "∂"
.n←20;m←24
∂(n)⊗⊗puzz3a ← mapcar[[λv: prup[$$(1 2 3 4 5 6)$, v]], puzz1]⊗
where
∂(n)⊗⊗prup[u, v] ← qif qn u qthen qNIL qelse [qa u . qa v] . prup[qd u, qd v]⊗,
and
∂(n)⊗⊗puzz4a ← mapcar[[λs: sublis[puzz2, s]], puzz3]⊗
where
∂(n)⊗⊗sublis[z, a] ← ⊗
∂(m)⊗⊗qif qat z qthen {assoc[z, a]}[λzz: qif qn zz qthen z qelse qd zz]⊗
∂(m)⊗⊗qelse sublis[qa z, a] . sublis[qd z, a]⊗.
.end
Of course we have ⊗puzz3_=_puzz3a and ⊗puzz4_=_puzz4a.
A more sophisticated representation of face cycles and partial towers
makes a factor of ten speedup without changing the basic search algorithm. Here
a face cycle is represented by 16 bits in a word, four for each face, a particular
one of which being turned on tells us the color of the face. If we %3bool-or%1
these words together for the blocks in a partial tower we get a word which
tells us for each face of the tower what colors have been used. A
particular face cycle from the next block can be added to the tower if
the %3bool-and%1 of its word with the word representing the tower is zero.
We represent a position by a list of words representing its partial
towers with $0 as the last element and the highest partial tower as the
first element. The virtue of this representation is that it makes
the description of the algorithm short.
The initial position is $$(0)$. The new ⊗puzz can be formed from the
old one by the assignment
⊗⊗⊗puzza ← mapcar[λu: mapcar[bool-cycle, u], puzz]⊗
where
.begin nofill group turnon "∂"
.n←16
!fcnboolcycle& ∂(n)⊗⊗bool-cycle v ← qif qn v qthen $0 qelse bool-color qa v + $16 q* bool-cycle qd v⊗
!fcnboolcolor& ∂(n)⊗⊗bool-color x ← qif x = $R qthen $1 qelse if x = $W qthen
$2 qelse qif x = $G qthen $4 qelse $$8$⊗.
.end
Now we need new versions of ⊗lose, ⊗ter, and ⊗successors. These are
.begin nofill group turnon "∂"
.n←16
!fcnlose&puzza ∂(n)⊗⊗lose p ← qfalse , ⊗
!fcnter&puzza ∂(n)⊗⊗ter p ← [length p = 5]⊗,
!fcnsuccessors&puzza ∂(n)⊗⊗successors p ← mapchoose[[λx: [qa p %3bool-and%* x] = $$0$], ⊗
∂(n)⊗⊗ [λx: [qa p %3bool-or%* x] . p], nth[puzza, length p]]⊗
.apart
where
.group
∂(n) ⊗⊗mapchoose[pred, fn, u] ← ⊗
∂(n+4) ⊗⊗qif qn u qthen qNIL⊗
!fcnmapchoose& ∂(n+4) ⊗⊗qelse qif pred qa u qthen fn[qa u] . mapchoose[pred, fn, qd u] ⊗
∂(n+4) ⊗⊗qelse mapchoose[pred, fn, qd u]⊗.
.end
⊗lose is trivial, because the ⊗mapchoose is used to make sure
that only non-losing new positions are generated by ⊗successors.
This version runs in a little less than one second on the KA-10. A greater
speedup can be made by the application of some mathematics. In fact, with
enough mathematics, extensive tree search is unnecessary in this problem.
.ss(minmax,Game trees.)
The positions that can be reached from an initial position in
a game form a tree, and deciding what move to make often involves
searching this tree. However, game trees are searched in a different
way than the trees we have looked at previously, because the opposing interests
of the players makes it not a search for a joint line of play that
will lead to the first player winning, but rather a search for a
strategy that will lead to a win regardless of what the other player
does. In this section we discuss two methods for searching a game tree.
The first is a simple minimax search which examines all lines of play
before making a decision. The second makes use of a heuristic known as
the ααβ-heuristic to prune the search space. In both cases the basic recursive
structure of the computation is presented in a game independent fashion
by letting the game be characterized by a collection of functions which
satisfy some general conditions. The game of 2-dimensional Tic_Tac_Toe
will be used as an example application of these game tree searching
techniques.
In the simplest situation the game is characterized by a function
⊗successors that gives the positions that can be reached in one
move, a predicate ⊗ter that tells when a position is to be
regarded as terminal for the given analysis, and a function
⊗imval that gives a number approximating the value of a terminal
position to one of the players. We shall call this player the
maximizing player and his opponent the minimizing player. Usually,
the numerical values arise, because the search cannot be carried out
to the end of the game, and the analysis stops with reasonably static
positions that can be evaluated by some rule. Naturally, the
function ⊗imval is chosen to be easy to calculate and to
correlate well with the probability that the maximizing player can
win the position.
Consider the game of Tic Tac Toe played in
2-dimensions. A position is determined by knowing which of the nine
squares contain X's, O's, or blanks.
The successors of a position
in the case that it is the X-players turn to move are all those positions
obtained by putting an X in a blank square. A position is terminal if
there are three X's or three O's on a line or diagonal, or
if there are no blank squares.
If we take the X-player to be
the maximizing player then we could assign values to the terminal positions
as follows.
In the case of three X's the value
is 1, in the case of three O's the value is -1 and otherwise it is 0.
The simple minimax rule for finding the correct move in a position
uses a pair of programs ⊗⊗(vmin,_vmax)⊗. ⊗vmax gives the value of a position
to the maximizing player by using ⊗imval if the position is terminal and
taking the max of the values of the successor positions to the minimizing player
otherwise. ⊗vmin similiarly gives the value of a position to the minimizing
player.
For this we want programs for getting the maximum or the
minimum of a function on a list, and they are defined as follows:
.begin nofill group
!fcnmaxlis& ⊗⊗⊗maxlis[u, f] ← qif qn u qthen -∞ qelse max[f[qa u], maxlis[qd u, f]]⊗,
!fcnminlis& ⊗⊗⊗minlis[u, f] ← qif qn u qthen ∞ qelse min[f[qa u], minlis[qd u, f]]⊗.
.end
Here the symbols -∞ and ∞ represent numbers that are smaller and
larger than any actual values that will occur in evaluating ⊗f.
If these numbers are not available, then it is necessary to prime
the program with the values of ⊗f applied to the first element
of the list, and the programs are then meaningless for null lists.
Iterative versions of these programs are generally better; we give only
the iterative version of ⊗maxlis, namely
.begin nofill group
⊗⊗⊗ maxlis[u, f] ← maxlisa[u, -∞, f], ⊗
!fcnmaxlis&it
⊗⊗⊗maxlisa[u, x, f] ← qif qn u qthen x qelse maxlisa[qd u, max[x, f[qa u]], f]⊗.
.end
We now have
.begin nofill group
!fcnvmax& ⊗⊗⊗vmax p ← qif ter p qthen imval p qelse maxlis[successors p, vmin]⊗,
!fcnvmin& ⊗⊗⊗vmin p ← qif ter p qthen imval p qelse minlis[successors p, vmax]⊗.
.end
The best move is determined by the pair of programs (⊗movemax, ⊗movemin).
The key to the computation is the pair of programs
(⊗bestmaxa, ⊗bestmina) which determine the optimal
move from a list of moves. They call each other recursively and differ only in that
one is for when the maximizing player is to move and the other is for when
the minimizing player is to move.
The argument ⊗bestmove is the best move found so far and ⊗bestval is value of the
resulting position as computed by ⊗f. Here are the definitions.
.begin nofill group
!fcnmovemax& ⊗⊗⊗movemax p ← bestmax[succesors p, vmin]⊗,
!fcnmovemin& ⊗⊗⊗movemin p ← bestmin[succesors p, vmax]⊗,
.apart
where
.group
⊗⊗bestmax[u, f] ← bestmaxa[qd u, qa u, f[qa u], f]⊗,
!fcnbextmax&
⊗⊗bestmaxa[u, bestmove, bestval, f] ← qif qn u qthen bestmove⊗
⊗⊗qelse qif f[qa u] ≤ bestval qthen bestmaxa[qd u, bestmove, bestval, f]⊗
⊗⊗qelse bestmaxa[qd u, qa u, f[qa u], f]⊗,
.apart
and
.group
⊗⊗bestmin[u, f] ← bestmina[qd u, qa u, f[qa u], f]⊗,
!fcnbestmin&
⊗⊗bestmina[u, bestmove, bestval, f] ← qif qn u qthen bestmove⊗
⊗⊗qelse qif f[qa u] ≥ bestval qthen bestmina[qd u, bestmove, bestval, f]⊗
⊗⊗qelse bestmina[qd u, qa u, f[qa u], f]⊗.
.end
This straight minimax computation of the best move does
much more computation in general than is necessary. The simplest
way to see this is from the move tree of Figure_{fig movetree}.
.BEGIN SELECT D; GROUP;
.NOFILL
.PREFACE 0
.MILLPREFACE ← 0
.TURNOFF "α"; TURNON "∂";
.SKIP 3
∂(42)8
∂(36)max∂(39)≤'
∂(37)≤'∂(38)≥∂(38)ααα 1
∂(32)min ∂(35)≤'∂(39)`≥
∂(33)≤' ∂(42)6
∂(32)'∂(32)≥
∂(33)`≥ ∂(42)9
∂(35)`≥∂(39)≤'
∂(37)`≥∂(38)'∂(38)ααα x
∂(39)`≥
∂(42)x
.SKIP 2
.END
!figmovetree Move tree showing how simple minimax does too much work.!
We see from this figure that it is unnecessary to examine the moves marked
_%Cx%1_ because their values have no effect on the value of the game or on the
correct move since the presence of the %c9%* is sufficient information at this
point to show that the move leading to the vertex preceding it should not
be chosen by the minimizing player.
The general situation is that it is unnecessary to examine further
moves from a position once a move is found that refutes moving to that
position in the first place. This idea is called the ααβ-heuristic.
As an example of how this heuristic might be used, we describe three collections
of programs: ⊗⊗(valmax,_valmin)⊗, ⊗⊗(linemax,_linemin)⊗ and ⊗⊗(treemax,_treemin)⊗.
The programs ⊗⊗(valmax,_valmin)⊗ return the value of the game to the corresponding
player, ⊗⊗(linemax,_linemin)⊗ return the value and a line of play obtaining that
value, and ⊗⊗(treemax,_treemin)⊗ return the value and a "proof" that this is the
optimal value for the corresponding player.
The "proof" consists of two trees of moves and terminal values giving a strategy
guaranteeing in one case that the value of the game is at least the value returned
and in the other case that it is at most the value returned.
Each pair of programs uses an auxiliary pair of programs which do the
processing of successor lists. Thus in each group there are four
mutually interacting programs.
The use of the ααβ-heuristic is the same in each group,
they differ in the information that they are carrying around as the search
progresses. As before we assume that the functions ⊗successors, ⊗ter, and
⊗imval characterize the game.
For purposes of determining properties of ⊗valmax and friends, the program
⊗rectify can be assumed to compute the identity function. It is included in order
to allow a more efficient representation of the game and will be discussed in
the next section. ⊗ext is used to extract from a position
the move leading to that position.
The programs (⊗valmax, ⊗valmin) each take three arguments: a
position ⊗p, and the parameters ⊗alpha and ⊗beta. ⊗alpha is the maximum
value that can be guaranteed the maximizing player based on the search so far,
and ⊗beta is the least value that can be guaranteed the minimizing player
based on the search so far. Initially ⊗alpha is essentially -∞ and ⊗beta is ∞.
⊗valmax works as follows. It checks to see if the position is terminal, and if
so returns ⊗imval_p directly, otherwise it asks ⊗vmaxlis for the best value
(with respect to ⊗alpha and ⊗beta) among the successor positions.
⊗vmaxlis goes through a list of positions, computes the value of each one
to the minimizing player, using ⊗valmin, and does one of three things.
If the value is not greater than ⊗alpha, it is ignored as we are
guaranteed to be able to do as well or better by a previously found move.
If the value is not less than ⊗beta then the computation is aborted
as ⊗beta is the best that the maximizing player can
hope for and the minimizing player would not allow this line of play
if it produced a higher value.
If the value
is greater than ⊗alpha but less than ⊗beta then this is a better choice for
the maximizing player and ⊗alpha is updated.
When the list is exhausted ⊗alpha represents the maximum value that
the maximizing player can be guaranteed starting from the position that gave rise
to the initial list of moves.
⊗valmin works in a dual fashion. The definitions are:
.begin nofill turnon "∂" turnoff "{}"
.n←16;m←20
.group
∂(n)⊗⊗valmax[p, alpha, beta] ← ⊗
!fcnvalmax& ∂(m)⊗⊗qif ter[rectify p, alpha, beta] qthen imval p⊗
∂(m)⊗⊗qelse vmaxlis[successors p, alpha, beta]⊗
∂(n)⊗⊗vmaxlis[u, alpha, beta] ← ⊗
∂(m)⊗⊗qif qn u qthen alpha⊗
∂(m)⊗⊗qelse {valmin[qa u, alpha, beta]}[λs: ⊗
!fcnvmaxlis& ∂(m+4)⊗⊗qif ¬[s > alpha] qthen vmaxlis[qd u, alpha, beta]⊗
∂(m+4)⊗⊗qelse qif s < beta qthen vmaxlis[qd u, s, beta]⊗
∂(m+4)⊗⊗qelse beta]⊗
.apart
.group
∂(n)⊗⊗valmin[p, alpha, beta] ← ⊗
!fcnvalmin& ∂(m)⊗⊗qif ter[rectify p, alpha, beta] qthen imval p⊗
∂(m)⊗⊗qelse vminlis[successors p, alpha, beta]⊗
∂(n)⊗⊗vminlis[u, alpha, beta] ← ⊗
∂(n)⊗⊗qif qn u qthen beta⊗
∂(n)⊗⊗qelse {valmax[qa u, alpha, beta]}[λs: ⊗
!fcnvminlis& ∂(m+4)⊗⊗qif ¬[s > alpha] qthen alpha⊗
∂(m+4)⊗⊗qelse qif s < beta qthen vminlis[qd u, alpha, s]⊗
∂(m+4)⊗⊗qelse vminlis[qd u, alpha, beta]]⊗
.apart
.end
We see that ⊗(valmax,_valmin) are related to ⊗(vmax,_vmin) as follows:
.begin nofill turnon "∂" group
.n←20;m←28
∂(n)⊗⊗valmax[p,alpha,beta]=⊗
∂(m)⊗⊗qif vmax[p]≤alpha qthen alpha⊗
!eqneqvalmax ∂(m)⊗⊗qelse qif alpha<vmax[p]<beta qthen vmax[p]⊗
∂(m)⊗⊗qelse qif beta≤vmax[p] qthen beta⊗
.apart
.group
∂(n)⊗⊗valmin[p,alpha,beta]=⊗
∂(m)⊗⊗qif vmin[p]≤alpha qthen alpha⊗
!eqneqvalmin ∂(m)⊗⊗qelse qif alpha<vmin[p]<beta qthen vmin[p]⊗
∂(m)⊗⊗qelse qif beta≤vmin[p] qthen beta⊗
.apart
.end
Thus if we initialize ⊗valmax or ⊗valmin with a sufficiently small ⊗alpha
and a sufficiently large ⊗beta we will get the same answer as given by
the brute force search. If we miss, we can tell and try again with
a better estimate.
The programs (⊗linemax, ⊗linemin) take three arguments,
the same as for (⊗valmax, ⊗valmin). The additional argument ⊗line required
by ⊗(lmaxlis,_lminlis) corresponds to the first line of
play (list of moves) found which terminates in a position of value ⊗alpha for
⊗linemax or ⊗beta for ⊗linemin. ⊗(lmaxlis,_lminlis) either pass ⊗line along
in the case that the value found is not an improvement, or construct a
new ⊗line from the one returned by ⊗(linemin,_linemax) in the case that it
leads to an improved value.
The result returned is the optimal value ⊗⊗cons⊗ed
onto the list of moves giving the first line of play found attaining that value.
The definitions are:
.begin nofill turnon "∂" turnoff "{}"
.n←16;m←20
.group
∂(n)⊗⊗linemax[p, alpha, beta] ← ⊗
!fcnlinemax& ∂(m)⊗⊗qif ter[rectify p, alpha, beta] qthen <imval p>⊗
∂(m)⊗⊗qelse lmaxlis[successors p, alpha . $$ALPHA-CUTOFF$, alpha, beta]⊗
∂(n)⊗⊗lmaxlis[u, line, alpha, beta] ← ⊗
∂(m)⊗⊗qif qn u qthen alpha . line⊗
∂(m)⊗⊗qelse {linemin[qa u, alpha, beta]}[λs: ⊗
!fcnlmaxlis& ∂(m+4)⊗⊗qif ¬[qa s > alpha] qthen lmaxlis[qd u, line, alpha, beta]⊗
∂(m+4)⊗⊗qelse qif qa s < beta qthen lmaxlis[qd u, ext qa u . qd s, qa s, beta]⊗
∂(m+4)⊗⊗qelse beta . line]⊗
.apart
.group
∂(n)⊗⊗linemin[p, alpha, beta] ← ⊗
!fcnlinemin& ∂(m)⊗⊗qif ter[rectify p, alpha, beta] qthen <imval p>⊗
∂(m)⊗⊗qelse lminlis[successors p, beta . $$BETA-CUTOFF$, alpha, beta]⊗
∂(n)⊗⊗lminlis[u, line, alpha, beta] ← ⊗
∂(n)⊗⊗qif qn u qthen beta . line⊗
∂(n)⊗⊗qelse {linemax[qa u, alpha, beta]}[λs: ⊗
!fcnlminlis& ∂(m+4)⊗⊗qif ¬[qa s > alpha] qthen alpha . line⊗
∂(m+4)⊗⊗qelse qif qa s < beta qthen lminlis[qd u, ext qa u . qd s, alpha, qa s]⊗
∂(m+4)⊗⊗qelse lminlis[qd u, line, alpha, beta]]⊗
.apart
.end
The programs (⊗treemax, ⊗treemin) take the same arguments as the
value and line versions do. The programs ⊗(tmaxlis,_tminlis) each take
two additional arguments, ⊗trmax and ⊗trmin. These are
move trees including terminal values, which are used to build the proofs
previously mentioned.
If a position ⊗p is non-terminal and ⊗u_=_successors_p then
⊗⊗tmaxlis[u,_qNIL,_qNIL,_αα,_β]⊗ returns a list ⊗⊗<val,_pfmax,_pfmin>⊗ where
one of the following is true:
.BEGIN INDENT 4,8
.item←0
#.) ⊗val ≤ αα and ⊗pfmin is a proof that the value of ⊗p to the maximizing
player is at most ⊗val.
#.) αα < ⊗val < β, ⊗pfmax is a proof that the value of ⊗p to the maximizing
player is at least ⊗val and ⊗pfmin is a proof that it is at most ⊗val.
#.) β ≤ ⊗val and ⊗pfmax is a proof that the value of ⊗p to the maximizing player is
at least ⊗val.
.END
Similarly ⊗⊗treemin[u,_qNIL,_qNIL,_αα,_β]⊗ returns a list ⊗⊗<val,_pfmax,_pfmin>⊗
where the value is now relative to the minimizing player.
Note that in the case ⊗val_≤_αα_(≥_β) we make no requirement of
⊗pfmax (⊗pfmin). This is in these cases the searches were probably incomplete
and the resulting proof would make no sense. The definitions of are:
.begin nofill turnon "∂" turnoff "{}"
.n←12;m←16
.group
∂(n)⊗⊗treemax[p, alpha, beta] ← ⊗
!fcntreemax& ∂(m)⊗⊗qif ter[rectify p, alpha, beta] qthen {imval p}[λv: <v, <v>, <v>>]⊗
∂(m)⊗⊗qelse tmaxlis[successors p, alpha . $$ALPHA-CUTOFF$, qNIL, alpha, beta]⊗
∂(n)⊗⊗tmaxlis[u, trmax, trmin, alpha, beta] ← ⊗
∂(m)⊗⊗qif qn u qthen <alpha, trmax, trmin>⊗
∂(m)⊗⊗qelse {treemin[qa u, alpha, beta]}[λs: ⊗
∂(m+4)⊗⊗qif ¬[qa s > alpha] qthen ⊗
!fcntmaxlis& ∂(m+8)⊗⊗tmaxlis[qd u, trmax, [ext qa u . qadd s] . trmin, alpha, beta]⊗
∂(m+4)⊗⊗qelse qif qa s < beta qthen ⊗
∂(m+8)⊗⊗tmaxlis[qd u, ext qa u . qad s, [ext qa u . qadd s] . trmin, qa s, beta]⊗
∂(m+4)⊗⊗qelse <beta, ext qa u . qad s, qNIL>]⊗
.apart
.group
∂(n)⊗⊗treemin[p, alpha, beta] ← ⊗
!fcntreemin& ∂(m)⊗⊗qif ter[rectify p, alpha, beta] qthen {imval p}[λv: <v, <v>, <v>>]⊗
∂(m)⊗⊗qelse tminlis[successors p, qNIL, beta . $$BETA-CUTOFF$, alpha, beta]⊗
∂(n)⊗⊗tminlis[u, trmax, trmin, alpha, beta] ← ⊗
∂(m)⊗⊗qif qn u qthen <beta, trmax, trmin>⊗
∂(m)⊗⊗qelse {treemax[qa u, alpha, beta]}[λs: ⊗
∂(m+4)⊗⊗qif ¬[qa s > alpha] qthen <alpha, qNIL, ext qa u . qadd s>⊗
!fcntminlis& ∂(m+4)⊗⊗qelse qif qa s < beta qthen ⊗
∂(m+8)⊗⊗tminlis[qd u, [ext qa u . qad s] . trmax, ext qa u . qadd s, alpha, qa s]⊗
∂(m+4)⊗⊗qelse tminlis[qd u, [ext qa u . qad s] . trmax, trmin, alpha, beta]]⊗
.apart
.end
We now describe how a move tree, ⊗pf, represents a proof of the sort
required above. There are four cases.
1) ⊗pf is a proof that the value of ⊗p to the maximizing player is
at least ⊗val if one of the following holds:
(i) ⊗p is terminal and ⊗⊗pf_=_<imval_p>⊗ and ⊗⊗imval_p_≥_val⊗
(ii) ⊗p is not terminal and ⊗⊗pf_=_mv_._pf'⊗ where ⊗mv is a move leading
to ⊗⊗p'_ε_successors_p⊗ and ⊗pf' is a proof that the value of ⊗p' to the minimizing
player is at least ⊗val.
2) ⊗pf is a proof that the value of ⊗p to the minimizing player is at least ⊗val
if one of the following holds:
(i) ⊗p is terminal and ⊗⊗pf_=_<imval_p>⊗ and ⊗⊗imval_p_≥_val⊗.
(ii) ⊗p is not terminal and ⊗pf is a list of elements of the form
⊗⊗mv_._pf'⊗, one for each ⊗p'_ε_successors_p, such that ⊗mv is a move leading from
⊗p to ⊗p' and ⊗pf' is a proof that the value of ⊗p' to the maximizing player is
at least ⊗val.
Cases 3) and 4) are obtained from 1) and 2) by interchanging the words maximizing
and minimizing and reversing the sense of the inequalities throughout.
The ααβ algorithm can also be used to in the case that there is a way to
estimate the value of a position ⊗p. Suppose we estimate that
⊗⊗a_<_vmax_p_<_b⊗. Then if ⊗⊗valmax[p,_a,_b]_=_val⊗ with ⊗⊗a_<_val_<_b⊗ then
we win as we now have the correct value and hopefully the narrower range
caused even more pruning than usual. If ⊗⊗val_≤a⊗ then we must lower the
estimate of the value and try again. Similarly if ⊗⊗val_≥_b⊗ then we raise
the estimate.
The reduction in number of positions examined given by the ααβ algorithm
over the simple minimax algorithm depends on the order in which the moves are
examined. In the worst case, the moves happen to be examined in inverse order
of merit in every position on the tree, i.e. the worst move first. In that case,
there is no improvement over minimax. The best case is the one in which the
best move in every position is examined first. If we look ⊗n moves
deep on a tree that has ⊗k successors to each position, then minimax looks
at ⊗⊗k%5n⊗ positions while ααβ looks at about only ⊗⊗k%5n/2⊗. Thus a
program that looks at 10%54%1 moves with ααβ might have to look at 10%58%1
with minimax. For this reason, game playing programs using ααβ make a big
effort to include as good as possible an ordering of moves into the ⊗successors
function. When there is a deep tree search to be done, the way to make the
ordering is with a short look-ahead to a much smaller depth than the main
search. Still shorter look-aheads are used deeper in the tree, and beyond
a certain depth, non-look-ahead ordering methods are of decreasing complexity.
A version of ααβ incorporating optimistic and pessimistic evaluations
of positions was first proposed by McCarthy about 1958. Edwards and Hart at
M.I.T. about 1959 proved that the present version of ααβ works and calculated the
improvement it gives over minimax. The first publication, however, was
Brudno [1963]. For additional discussion of ααβ techinques see
Nilsson[1971], Knuth and Moore[1975] or Winston[1977].
It is worth noting that ααβ was not used in the early chess
playing programs in spite of the fact that it is clearly used in any human
play. Its non-use, therefore, represents a failure of self-observation.
Very likely, there are a number of other algorithms used in human thought
that we have not noticed and incorporated in our programs. To the extent
that this is so, artificial intelligence will be %2a posteriori%1 obvious
even though it is %2a priori%1 very difficult.
.ss(trick,The hidden board trick.)
The program ⊗rectify is used to implement a particular method
of representing a game known as the "hidden board trick". It basically
relies on side effects to produce an alternate representation of a given
position when it is needed. Here
a position is represented by a list of moves leading to
it with the most recent move at the head of the list and the first move
of the game at the end of the list. This is an efficient representation
with respect to storage for two reasons. One is that lists of positions
will frequently have only the last few moves differing and can be represented
as merging list structures. The second is that other representations frequently
take the form of a collection of tables and the representation of each position
requires a lot of space. However it is often easier to compute the
successors, determine if a position is terminal, and compute its value
using a more spacious representation. To take advantage of this fact
we keep around a representation of the position of current interest,
the hidden board, in a form convenient for doing these computations.
A list of moves leading to that position is also kept.
The function ⊗rectify is used to make a new
position current. It returns the new position
unchanged, but has the side effect of making it the current position
as far as the alternate representation is concerned. This is accomplished
by using ⊗commontail to
find out where in the past the current and new positions meet ,
backing up to this position and then moving forward along the path
of the new position. This requires the additional game dependent functions
⊗revert for taking back moves, and ⊗update for making moves. The programs
for ⊗rectify and its auxiliaries follow.
.BEGIN NOFILL turnon "∂"
.n←16
.group
∂(n)⊗⊗ rectify p ← ⊗
∂(n)⊗⊗ qprog [z, q]⊗
∂(n)⊗⊗ q ← commontail[p, p1]⊗
∂(n)⊗⊗ $$L1:$ qif q = p1 qthen qgo $$L2$⊗
∂(n)⊗⊗ revert[]⊗
!fcnrectify& ∂(n)⊗⊗ qgo $$L1$⊗
∂(n)⊗⊗ $$L2:$ z ← listsubt[p, p1]⊗
∂(n)⊗⊗ $$L3:$ qif qn z qthen return p⊗
∂(n)⊗⊗ update qa z⊗
∂(n)⊗⊗ z ← qd z⊗
∂(n)⊗⊗ qgo $$L3$⊗
.apart
!fcncommontail& ∂(n)⊗⊗ commontail[u, v] ← reverse commonhead[reverse u, reverse v]⊗
.group
∂(n)⊗⊗ commonhead[u, v] ← ⊗
!fcncommonhead& ∂(n)⊗⊗ qif qn u ∨ qn v ∨ ¬[qa u = qa v] qthen qNIL⊗
∂(n)⊗⊗ qelse qa u . commonhead[qd u, qd v]⊗
.apart
.group
∂(n)⊗⊗ listsubt[u, v] ← listsubta[u, length u - length v, qNIL]⊗
!fcnlistsubt&
∂(n)⊗⊗ listsubta[u, n, z] ← ⊗
∂(n)⊗⊗ qif n = 0 qthen z qelse listsubta[qd u, sub1 n, qa u . z]⊗
.apart
.END
.ss(tictactoe,2-dimensional Tic Tac Toe.)
As a simple example of how the programs described in the previous
two sections can be used we give a set of
programs characterizing the game of 2-dimensional Tic Tac Toe and show the results
of some computations using the programs employing the
ααβ-heuristic. This characterization of Tic Tac Toe improves the efficiency
of the search routines by doing some precomputing of position values and
thus pruning and ordering the list of successors for a given position.
The nine
squares of the Tic Tac Toe board are numbered from left to right starting
from the top row. The eight lines are numbered similarly with the horizontal
lines first, then vertical, then the two diagonals
There are several global arrays and variables. These are initialized
by the programs ⊗commence and ⊗newgame. The ith element of ⊗lines is a list
of lines containing the ith square. ⊗xcount tells how many $$X$'s are on a given
line, ⊗ocount does the same for $$O$'s. ⊗p1 is the list of moves leading to the
position represented by the state of the global variables. (A move is represented
by the number of the square filled.)_ ⊗xs, ⊗os, and ⊗bs are lists of the squares
containing $$X$'s, $$O$'s, and blanks respectively. ⊗w tells whose turn it is to
move. If qT then it is the $$O$-players turn, if qNIL then it is the $$X$-players
turn. ⊗level is the number of moves so far (the length of ⊗p1). ⊗count is
the total number of moves examined.
For the $$X$-player a winning position has value $$10$-⊗level, any other
terminal position has value $0. For the $$O$-player a winning position has value
⊗⊗level-⊗$10 and any other terminal position has value $0.
A position is considered terminal if there are no blank spaces left,
or if ⊗⊗$$10$_-_level_≤_αα⊗, or if ⊗⊗-$$10$_+_level_≥β⊗,
or if it is the $$X$-players
turn to move and ⊗xcount is $3 for some line, or if it is the $$O$-players turn
and ⊗ocount is $3 for some line.
⊗successors uses ⊗sort and its auxiliaries to
prune and sort the list of possible moves from a non-terminal
position according to the following rules. If some move is a win then return a
list containing only that move, otherwise if some move is required to keep the
opponent from winning then that is returned as the single possibility, otherwise
if some move is a double-threat (creates two winning moves for the player)
then it is returned as the only possibility, otherwise a list of all possible
moves is returned with the threats (moves creating a winning move for the player)
at the front of the list.
The programs ⊗revert and ⊗update take back and make moves in the obvious
way.
.BEGIN NOFILL turnon "∂"
.n←8
.group
Here are the definitions: (note that the numbers are octal)
∂(n)⊗⊗ commence[] ← ⊗
∂(n)⊗⊗ qprog []⊗
∂(n)⊗⊗ array[lines, qT, 12]⊗
∂(n)⊗⊗ array[xcount, fixnum, 11]⊗
∂(n)⊗⊗ array[ocount, fixnum, 11]⊗
∂(n)⊗⊗ store[lines 1, $$(1 4 7)$]⊗
∂(n)⊗⊗ store[lines 2, $$(1 5)$]⊗
!fcncommence& ∂(n)⊗⊗ store[lines 3, $$(1 6 10)$]⊗
∂(n)⊗⊗ store[lines 4, $$(2 4)$]⊗
∂(n)⊗⊗ store[lines 5, $$(2 5 7 10)$]⊗
∂(n)⊗⊗ store[lines 6, $$(2 6)$]⊗
∂(n)⊗⊗ store[lines 7, $$(3 4 10)$]⊗
∂(n)⊗⊗ store[lines 10, $$(3 5)$]⊗
∂(n)⊗⊗ store[lines 11, $$(3 6 7)$]⊗
.apart
!fcnext& ∂(n)⊗⊗ ext p ← qa p⊗
.group
∂(n)⊗⊗ newgame[] ← ⊗
∂(n)⊗⊗ qprog [n]⊗
∂(n)⊗⊗ n ← 0⊗
∂(n)⊗⊗ $$L:$ n ← add1 n⊗
∂(n)⊗⊗ store[xcount n, 0]⊗
∂(n)⊗⊗ store[ocount n, 0]⊗
∂(n)⊗⊗ qif n < 10 qthen qgo $$L$⊗
!fcnnewgame& ∂(n)⊗⊗ p1 ← qNIL⊗
∂(n)⊗⊗ xs ← qNIL⊗
∂(n)⊗⊗ os ← qNIL⊗
∂(n)⊗⊗ bs ← $$(1 2 3 4 5 6 7 10 11)$⊗
∂(n)⊗⊗ w ← qNIL⊗
∂(n)⊗⊗ level ← 0⊗
∂(n)⊗⊗ count ← 0⊗
∂(n)⊗⊗ return $$(NEW GAME)$⊗
.apart
.group
∂(n)⊗⊗ ter[p, alpha, beta] ← ⊗
∂(n)⊗⊗ ¬qn p⊗
∂(n)⊗⊗ ∧ [level = 11⊗
∂(n)⊗⊗ ∨ 11 - level < alpha⊗
∂(n)⊗⊗ ∨ -11 + level > beta⊗
!fcnter&tic ∂(n)⊗⊗ ∨ [qprog [n]⊗
∂(n)⊗⊗ n ← 0⊗
∂(n)⊗⊗ $$L2:$ n ← add1 n⊗
∂(n)⊗⊗ qif 3 = [qif w qthen xcount n qelse ocount n] qthen ⊗
∂(n)⊗⊗ return qT⊗
∂(n)⊗⊗ qif n < 10 qthen qgo $$L2$⊗
∂(n)⊗⊗ return qNIL]]⊗
.apart
.group
∂(n)⊗⊗ imval p ← ⊗
∂(n)⊗⊗ qif w qthen ⊗
∂(n)⊗⊗ [qprog [n]⊗
∂(n)⊗⊗ n ← 0⊗
∂(n)⊗⊗ $$L3:$ n ← add1 n⊗
!fcnimval& ∂(n)⊗⊗ qif 3 = xcount n qthen return 12 - level⊗
∂(n)⊗⊗ qif n < 10 qthen qgo $$L3$ qelse return 0]⊗
∂(n)⊗⊗ qelse qprog [n]⊗
∂(n)⊗⊗ n ← 0⊗
∂(n)⊗⊗ $$L4:$ n ← add1 n⊗
∂(n)⊗⊗ qif 3 = ocount n qthen return -12 + level⊗
∂(n)⊗⊗ qif n < 10 qthen qgo $$L4$ qelse return 0⊗
.apart
!fcnsuccessors&tic ∂(n)⊗⊗ successors p ← sort mapcar[[λx: x . p], bs]⊗
.group
∂(n)⊗⊗ revert[] ← ⊗
∂(n)⊗⊗ qprog [a]⊗
∂(n)⊗⊗ level ← sub1 level⊗
∂(n)⊗⊗ bs ← qa [qif w qthen xs qelse os] . bs⊗
∂(n)⊗⊗ qif w qthen xs ← qd xs qelse os ← qd os⊗
∂(n)⊗⊗ a ← lines qa p1⊗
!fcnrevert& ∂(n)⊗⊗ $$L5:$ qif qn a qthen qgo $$L6$⊗
∂(n)⊗⊗ qif w qthen store[xcount qa a, sub1 xcount qa a]⊗
∂(n)⊗⊗ qelse store[ocount qa a, sub1 ocount qa a]⊗
∂(n)⊗⊗ a ← qd a⊗
∂(n)⊗⊗ qgo $$L5$⊗
∂(n)⊗⊗ $$L6:$ w ← ¬w⊗
∂(n)⊗⊗ p1 ← qd p1⊗
∂(n)⊗⊗ return qNIL⊗
.apart
.group
∂(n)⊗⊗ update m ← ⊗
∂(n)⊗⊗ qprog [a]⊗
∂(n)⊗⊗ level ← add1 level⊗
∂(n)⊗⊗ qif w qthen os ← m . os qelse xs ← m . xs⊗
∂(n)⊗⊗ bs ← delete[m, bs]⊗
∂(n)⊗⊗ p1 ← m . p1⊗
!fcnupdate& ∂(n)⊗⊗ count ← add1 count⊗
∂(n)⊗⊗ a ← lines m⊗
∂(n)⊗⊗ $$L7:$ qif qn a qthen qgo $$L8$⊗
∂(n)⊗⊗ qif w qthen store[ocount qa a, add1 ocount qa a]⊗
∂(n)⊗⊗ qelse store[xcount qa a, add1 xcount qa a]⊗
∂(n)⊗⊗ a ← qd a⊗
∂(n)⊗⊗ qgo $$L7$⊗
∂(n)⊗⊗ $$L8:$ w ← ¬w⊗
∂(n)⊗⊗ return[]⊗
.apart
!fcnsort&tic ∂(n)⊗⊗ sort u ← sorta[u, qNIL, qNIL]⊗
.group
∂(n)⊗⊗ sorta[u, th, ord] ← ⊗
∂(n)⊗⊗ qif qn u qthen [th * ord]⊗
∂(n)⊗⊗ qelse qif win qa u qthen <qa u>⊗
!fcnsorta&tic ∂(n)⊗⊗ qelse qif answer qa u qthen sortb[qd u, qa u]⊗
∂(n)⊗⊗ qelse qif doubleth qa u qthen sortc[qd u, qa u]⊗
∂(n)⊗⊗ qelse qif threat qa u qthen sorta[qd u, qa u . th, ord]⊗
∂(n)⊗⊗ qelse sorta[qd u, th, qa u . ord]⊗
.apart
∂(n)⊗⊗ sortb[u, m] ← ⊗
!fcnsortb&tic ∂(n)⊗⊗ qif qn u qthen <m> qelse qif win qa u qthen <qa u> qelse sortb[qd u, m]⊗
.group
∂(n)⊗⊗ sortc[u, m] ← ⊗
∂(n)⊗⊗ qif qn u qthen <m>⊗
!fcnsortc&tic ∂(n)⊗⊗ qelse qif win qa u qthen <qa u>⊗
∂(n)⊗⊗ qelse qif answer qa u qthen sortb[qd u, qa u]⊗
∂(n)⊗⊗ qelse sortc[qd u, m]⊗
.apart
∂(n)⊗⊗ win p ← qif w qthen orlis[[λx: 2 = ocount x], lines qa p]⊗
!fcnwin&tic ∂(n)⊗⊗ qelse orlis[[λx: 2 = xcount x], lines qa p]⊗
.group
∂(n)⊗⊗ answer p ← ⊗
!fcnanswer& ∂(n)⊗⊗ qif w qthen orlis[[λx: 2 = xcount x], lines qa p]⊗
∂(n)⊗⊗ qelse orlis[[λx: 2 = ocount x], lines qa p]⊗
.apart
.group
∂(n)⊗⊗ doubleth p ← ⊗
∂(n)⊗⊗ twolis[[λx: ⊗
!fcndoubleth& ∂(n)⊗⊗ 1 = [qif w qthen ocount x qelse xcount x]⊗
∂(n)⊗⊗ ∧ orlis[[λw: x ε lines w], delete[qa p, bs]]], ⊗
∂(n)⊗⊗ lines qa p]⊗
.apart
.group
∂(n)⊗⊗ twolis[pred, u] ← ⊗
!fcntwolis& ∂(n)⊗⊗ ¬qn u ∧ [[pred qa u ∧ orlis[pred, qd u]] ∨ twolis[pred, qd u]]⊗
.apart
.group
∂(n)⊗⊗ threat p ← ⊗
∂(n)⊗⊗ orlis[[λx: ⊗
!fcnthreat& ∂(n)⊗⊗ 1 = [qif w qthen ocount x qelse xcount x]⊗
∂(n)⊗⊗ ∧ orlis[[λw: x ε lines w], delete[qa p, bs]]], ⊗
∂(n)⊗⊗ lines qa p]⊗
.apart
.group
∂(n)⊗⊗ delete[x, u] ← ⊗
∂(n)⊗⊗ qif qn u qthen qNIL⊗
!fcndelete& ∂(n)⊗⊗ qelse qif x = qa u qthen qd u⊗
∂(n)⊗⊗ qelse qa u . delete[x, qd u]⊗
.apart
.END
.next page
Below we give some examples of the results returned by
⊗(lmin,lmax) and ⊗(tmin,tmax). In each case the situation is 2 moves
into a game where the $X player has moved first and hence it is the
$X players turn to move.
.BEGIN NOFILL select 6 indent 8,8 turnoff "_"
.group
Position numbering:
(1 2 3)
(4 5 6)
(7 10 11)
.apart
.group
Example 1.
Board: (O X _)
(_ _ _)
(_ _ _)
⊗⊗lmax[p1, $-1000, $$1000$] = ⊗(0 5 10 6 4 7 3 11)
⊗⊗tmax[p1,$-1000, $$1000$] =⊗
(0
(5 (10 6 (4 7 (3 11 0))))
((3 7 (4 11 (5 10 -2)))
(4 5 (11 7 (3 6 (10 0))))
(6 5 (11 3 (7 10 (4 0))))
(7 5 (11 10 (4 6 (3 0)) (3 6 (4 0)) (6 3 (4 0))))
(11 7 (4 5 (3 6 (10 0))))
(5 10 (11 4 (7 3 (6 0)))
(7 3 (11 6 (4 0)) (4 6 (11 0)) (6 4 (11 0)))
(3 7 (4 11 -2))
(4 6 (11 3 (7 0)) (7 3 (11 0)) (3 7 (11 0)))
(6 4 (7 3 (11 0))) )
(10 5 (11 7 (3 4 -2))) ) )
.apart
.group
Example 2.
Board: (O _ X)
(_ _ _)
(_ _ _)
⊗⊗lmax[p1, $-1000, $$1000$] = ⊗(3 11 6 7 5 10)
⊗⊗tmax[p1,$-1000, $$1000$] =⊗
(3
(11 (6 7 (5 10 3)))
((2 7 (4 11 (5 0)))
(4 5 (11 6 (2 0) (10 0) (7 0)))
(10 11 (5 7 (2 3)))
(5 7 (4 6 (11 0) (10 0) (2 0)))
(6 11 (5 7 (4 3)))
(7 5 (11 6 (10 3)))
(11 6 (7 5 (10 3))) ) )
.apart
.END